package com.hyper_yang.algorithmRecord.backTrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

// leetcode 46 全排列
public class Permutation {
    // 回溯: Tn = O(n * n!)
    public List<List<Integer>> permute1(int[] nums) {
        // 定义保存结果的 List
        ArrayList<List<Integer>> result = new ArrayList<>();
        // 用一个 ArrayList保存一组解
        ArrayList<Integer> solution = new ArrayList<>();
        // 回溯
        backTrack1(nums, result, solution, 0);

        return result;
    }

    // 定义辅助集合，保存已经用过的数
    HashSet<Integer> filledNums = new HashSet<>();

    private void backTrack1(int[] nums, List<List<Integer>> result, ArrayList<Integer> solution, int i) {
        int n = nums.length;
        // 递归退出条件
        if (i >= n) {
            result.add(new ArrayList<>(solution));
        } else {
            // 需要对 i位置选数填入，遍历数组中所有的数，取没有用过的数进行填充
            for (int j = 0; j < n; j++) {
                if (!filledNums.contains(nums[j])) {
                    solution.add(nums[j]);
                    filledNums.add(nums[j]);
                    // 递归调用处理下一个位置
                    backTrack1(nums, result, solution, i + 1);
                    // 回溯、回退状态
                    solution.remove(i);
                    filledNums.remove(nums[j]);
                }
            }
        }
    }

    // 空间优化
    public List<List<Integer>> permute(int[] nums) {
        // 定义保存结果的 List
        ArrayList<List<Integer>> result = new ArrayList<>();
        // 用一个 ArrayList保存一组解
        ArrayList<Integer> solution = new ArrayList<>();
        // 把 nums 赋值到 solution
        for (int num : nums)
            solution.add(num);
        // 回溯
        backTrack(result, solution, 0);

        return result;
    }

    private void backTrack(List<List<Integer>> result, ArrayList<Integer> solution, int i) {
        int n = solution.size();
        if (i >= n) {
            result.add(new ArrayList<>(solution));
        } else {
            for (int j = i; j < n; j++) {
                Collections.swap(solution, i, j);
                backTrack(result, solution, i + 1);
                Collections.swap(solution, i, j);
            }
        }
    }

    public static void main(String[] args) {
        Permutation solutions = new Permutation();
        Print(solutions.permute(new int[]{1, 2, 3}));
        solutions.permute(new int[]{0, 1});
        solutions.permute(new int[]{1});
    }

    public static void Print(List<List<Integer>> res) {
        for (List<Integer> r : res) {
            for (Integer num : r) {
                System.out.print(num + "\t");
            }
            System.out.println();
        }
    }
}
